Ja, guten Morgen.

Ja, wie am Mittwoch angekündigt, haben wir heute schon wieder was, was Spaß macht.

Zum Beispiel Kreise zerbröseln.

Ja, nämlich PNP-intermediäre Probleme. Ja, also für Intermediate gibt es halt kein richtig schönes deutsches Wort, sagen wir also Intermediär.

Ja, wann heißt ein Problem PNP-intermediär?

Beziehungsweise, na ja, sagen wir mal einfach ums Kürzer zu halten, NP-intermediär, was glaube ich auch eher Standard ist.

Naja, es heißt PNP-intermediär, wenn es also zwischen P, also tractability und NP-härte liegt.

Das heißt, wenn folgende Dinge gelten, erstens C ist mal in NP, gut, also noch härter als NP soll es nicht sein.

C ist aber nicht in P.

Und letztens C ist nicht NP-hart. Gut, offenbar wissen wir nicht, ob es NP-intermediäre Probleme gibt.

Zumindest wissen wir nicht, dass es NP-intermediäre Probleme gibt, denn wenn wir wüssten, dass es ein NP-intermediäres Problem gibt,

wüssten wir, dass P ungleich NP ist, denn dann hätten wir ja ein Problem, was in NP aber nicht in P wäre.

Wir vermuten aber, dass P nicht gleich NP ist, was dann also zumindest mal die Möglichkeit vernünftig erscheinen lässt,

dass es NP-intermediäre Probleme geben könnte.

Nur wie gesagt, wir kennen natürlich keins. Wenn wir eins kennen würden, dann hätten wir eben P ungleich NP gelöst.

Wir haben ein paar Kandidaten im Verdacht, aber sehr wenige.

Es ist irgendwann mal eine Liste veröffentlicht worden mit zwölf vermuteten NP-intermediären Problemen.

Von denen sind mittlerweile noch zwei als Kandidaten über. Das sind diese hier.

Das erste ist Grafisomorphie.

Das ist jetzt ein bisschen unterspezifiziert, aber das ist okay. Ich sage zum Beispiel nicht, ob ich damit gerichtete oder ungerichtete Grafen meine.

Das ist in der Tat auch egal. Grafisomorphie ist also einfach das Problem.

In die Hand geworfen zwei Grafen, muss man sagen, ob die isomorph sind oder nicht.

Klingt erst mal trivial, aber man muss sich überlegen, dass dieser Isomorphismus ja irgendwie die Knoten in den Grafen einander zuordnen muss.

Es ist klar, dass ich es in NP lösen kann. Ich rate einfach eine zuordnung, eine biaktive Zuordnung zwischen den Knoten und überprüfe dann, ob es ein Grafisomorphismus ist.

Besser als dieses Raten, was sich deterministisch in ein Durchprobieren all dieser Zuordnungen übersetzt, kann man es bis heute nicht.

Das ist ein Problem, das natürlich auch nicht ganz unwichtig ist, wie man sich denken kann. Es definiert also mittlerweile seine eigene Komplexitätsklasse.

Heutzutage gibt es erst mal zwischen P und NP die Klasse derjenigen Probleme, die gleich schwer sind wie das Grafisomorphieproblem.

Diese Klasse heißt GI.

Ich habe P Teilmenge, GI Teilmenge, NP. Wir wissen nicht natürlich, ob irgendeine dieser Inklusionen echt ist.

Das andere Problem, ebenfalls nicht ganz unwichtig, ist das Faktorisierungsproblem.

Da muss man aufpassen, wie man das formuliert. Das Problem an sich, ob eine Faktorisierung einer Zahl existiert, ist mittlerweile bekanntermaßen in P.

Das weiß man noch nicht so lange. Das ist das Primes-Problem. Eine Zahl hat dann keine Faktorisierung, wenn sie prim ist.

Das kann ich in polynomialer Zeit entscheiden, weiß man seit 2004.

Das ist also offensichtlich nicht das Problem Factoring. Worauf man eigentlich hinaus will, das Problem, von dem man im Moment noch hofft, dass es schwerer ist als zu entscheiden, ob eine Zahl prim ist,

ist eine Zahl tatsächlich zu faktorisieren. Davon, dass ich weiß, dass eine Zahl nicht prim ist, habe ich sie ja noch nicht faktorisiert.

Wenn ich eine Zahl effektiv faktorisieren könnte, hätten wir ein Problem.

Factoring ist dasselbe jetzt als Entscheidungsproblem. Da gebe ich rein als Eingabe ein Trippel von Zahlen.

Ich will entscheiden, ob N einen Faktor hat, der in dem durch die zweiten beiden Zahlen gegebenen Intervall liegt.

Man kann sich relativ schnell überlegen, dass wenn man das hier in P entscheiden könnte, man dann auch in P eine Zahl faktorisieren könnte.

Dann macht man mittels dieses Problems hier binäre Suche.

Man weiß nicht, ob diese Probleme tatsächlich PNP-intermediär sind. Wenn man überhaupt auf PNP-intermediäre Probleme hinaus will,

muss man angesichts des gegenwärtigen Wissenstandes also annehmen, dass P ungleich NP ist und dann unter dieser Annahme weitermachen.

Selbst unter dieser Annahme weiß man aber nicht, dass diese Probleme NP-intermediär sind. Man weiß aber, und das ist alles, was man da zur Zeit weiß, dass es NP-intermediäre Probleme gibt.

Das heißt, Thema der heutigen Stunde ist der Satz von Ladner. Der macht eben P ungleich NP als Voraussetzung.

Also wenn nicht P gleich NP ist, dann gibt es NP-intermediäre Probleme.

Das ist natürlich ein Äquivalenz, denn wenn es ein NP-intermediäres Problem gibt, dann ist per Definition des Wortes NP-intermediär P ungleich NP.

Der Beweis ist einer von denen, für die man schon ein bisschen irre sein muss. Der wird uns also den Rest der Sitzung beschäftigen.

Also, wir definieren die natürlichen Kandidaten, die haben wir da aufgelistet. Das heißt, das Problem, von dem jetzt hier gezeigt wird, dass es NP-intermediär ist, ist kein natürliches Problem, sondern ein künstliches.

Dieses künstliche Problem, das erzeugen wir durch Ausstopfen des Subproblems. Und zwar hängt das ab von einer Funktion, die auf natürlichen Zahlen, die wir nachher noch definieren.

Und diese Funktion gibt uns an, um wie viel wir das SAT-Problem ausstopfen, und zwar den Exponenten für die Länge des Ausstopfens.